package org.pupil.sort.logarithmicMachine;

import org.pupil.sort.ISort;
import org.pupil.sort.bubbleSort.BubbleSort;
import org.pupil.sort.insertionSort.InsertionSort;
import org.pupil.sort.selectionSort.SelectionSort;

/**
 * @Description: 对数器
 * 对数器的概念和使用：
 * 1，有一个你想要测的方法a，
 * 2，实现一个绝对正确但是复杂度不好的方法b（暴力解）
 * 3，实现一个随机样本产生器（长度也随机、值也随机）
 * 4，把方法a和方法b跑相同的输入样本，看看得到的结果是否一样
 * 5，如果有一个随机样本使得比对结果不一致，打印这个粗错样本进行人工干预，改对方法a和方法b
 * 6，当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。
 * @Author: pupil
 * @Date: 2024/08/01 上午 11:37
 */
public class Logarithm {


    public static void main(String[] args) {
        // 数据数组最大长度
        int N = 100;
        // 随机数组每个值，在1~V之间随机
        int V = 1000;
        // 测试次数
        int testNumber = 50000;
        System.out.println("测试开始");

        for (int i = 0; i < testNumber; i++) {
            int n  = (int) (Math.random()*N);
            int[] arr = randomArray(n, V);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);
            SelectionSort.selectionSort(arr1);
            BubbleSort.bubbleSort(arr2);
            InsertionSort.insertionSort(arr3);
            if (!sameArray(arr1,arr2) || !sameArray(arr1,arr3)){
                System.out.println("出错了！");
                ISort.print(arr);
                ISort.print(arr1);
                ISort.print(arr2);
                ISort.print(arr3);
            }
        }
        System.out.println("测试结束");
    }


    /**
     * 得到一个随机数组，长度是n
     *
     * @param n 数组长度
     * @param v 数组值的范围
     * @return 生成的随机数组
     */
    public static int[] randomArray(int n, int v) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            // Math.random() -> double -> [0,1)一个小数，0.37463473126、0.00123126
            // Math.random() * v -> double -> [0,v)一个小数，依然等概率
            // (int) ((Math.random() * v) -> int -> 0 1 2 3 ... v-1，等概率的！
            // (int) ((Math.random() * v) + 1 -> int -> 1 2 3 4 ... v，等概率的！
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }

    /**
     * 克隆数组，生成新的数组
     *
     * @param arr 数组
     * @return 克隆的数组
     */
    public static int[] copyArray(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    /**
     * 验证两个数组是否相等
     * @param arr1 数组1
     * @param arr2 数组2
     * @return
     */
    public static boolean sameArray(int[] arr1, int[] arr2) {
        int n = arr1.length;
        for (int i = 0; i < n; i++) {
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

}
